Chain rule for Kolmogorov complexity

The chain rule for Kolmogorov complexity is an analogue of the chain rule for information entropy, which states:

$H(X,Y) = H(X) %2B H(Y|X)$

That is, the combined randomness of two sequences X and Y is the sum of the randomness of X plus whatever randomness is left in Y once we know X. This follows immediately from the definitions of conditional and joint entropy fact from probability theory that the joint probability is the product of the marginal and conditional probability:

$P(X,Y) = P(X) P(Y|X) \,$

The equivalent statement for Kolmogorov complexity does not hold exactly; it is only true up to a logarithmic factor:

$K(X,Y) = K(X) %2B K(Y|X) %2B O(\log(K(X,Y)))$

(An exact version, KP(X, Y) = KP(X) + KP(Y|X*) + O(1), holds for the prefix complexity KP, where X* is a shortest program for X.)

It states that the shortest program to reproduce X and Y is using a program to reproduce X and a program to reproduce Y given X, plus at most a logarithmic factor. Using this statement one can define an analogue of mutual information for Kolmogorov complexity.

Proof

The ≤ direction is obvious: we can write a program to produce x and y by concatenating a program to produce x, a program to produce y given access to x, and (whence the log term) the length of one of the programs, so that we know where to separate the two programs for x and y|x (log(K(x, y)) upper-bounds this length).

The ≥ direction is rather more difficult. The key to the proof is the construction of the set $A = \{(u,z)�: K(u,z) \le K(x,y)\}$ ; that is, the construction of the set of all pairs $(u,z)$ such that the shortest input (for a universal Turing machine) that produces $(u,z)$ (and some way to distinguish $u$ from $z$ ) is shorter than the shortest producing $(x,y)$ . We will also need $A_x = \{z: K(x,z) \le K(x,y)\}$ , the subset of $A$ where $x = u$ . Enumerating $A$ is not hard (although not fast!). In parallel, simulate all $2^{K(x,y)}$ programs with length $\le K(x,y)$ . Output each $u,z$ as the simulated program terminates; eventually, any particular such $u,z$ will be produced. We can restrict to A_x simply by ignoring any output where $u \ne x$ . We will assume that the inequality does not hold and derive a contradiction by finding a short description for K(x) in terms of its index in the enumeration of a subset of A.

In particular, we can describe y by giving the index in which y is output when enumerating A_x (which is less than or equal to |A_x|) along with x and the value of K(x, y). Thus,

$K(y|x) \le \log(|A_x|) %2B O(\log(K(x,y))) %2B O(1) \,$

where the O(1) term is from the overhead of the enumerator, which does not depend on x or y.

Assume by way of contradiction

$K(y|x) > K(x,y) - K(x) %2B O(\log(K(x,y))) \,$

for some $x,y$ .

Combining this with the above, we have

$\log(|A_x|) %2B O(\log(K(x,y))) %2B O(1) \ge K(y|x) > K(x,y) - K(x) %2B O(\log(K(x,y))) \,$

So for any constant c and some x, y,

$\log(|A_x|) \ge K(x,y) - K(x) %2B c \log(K(x,y)) \,$

Let

$e = K(x,y) - K(x) %2B c \log K(x,y);\quad |A_x| \ge 2^e.$

Now, we can enumerate a set of possible values for $x$ by finding all $u$ such that $|A_u| > 2^e$ -- list only the $u$ such that $y$ is output after more than $2^e$ other values when enumerating $A_u = \{ z: K(u,z) \le K(x,y) \}$ . $x$ is one such $u$ . Let $U$ be the set of all such $u$ . We can enumerate $U$ by enumerating each $A_u$ (in parallel, as usual) and outputting a $u$ only when $y$ would be output for $A_u$ and more than $2^e$ other values for the $A_u$ would be output. Note that given $K(x,y)$ , $e$ and the index of $x$ in $U$ we can enumerate $U$ to recover $x$ .

Note that $\{(u,z)�: u \in U, z \in A_u\}$ is a subset of $A$ , and $A$ has at most $2^{K(x,y)}$ elements, since there are only that many programs of length $K(x,y)$ . So we have:

$|U| < \frac{|A|}{2^e} \le \frac{2^{K(x,y)}}{2^e}$

where the first inequality follows since each element of $U$ corresponds to an $A_u$ with strictly more than $2^e$ elements.

But this leads to a contradiction:

$K(x) < \log(K(x,y)) %2B \log(e) %2B \log(|U|) \le \log(K(x,y)) %2B \log(e) %2B K(x,y) - e$

which when we substitute in $e$ gives

$K(x) < \log(K(x,y)) %2B \log(K(x,y) %2B K(x) %2B \log(K(x,y)) %2B K(x,y) - K(x,y) %2B K(x) - c \log K(x,y)$

which for large enough $c$ gives $K(x) < K(x)$ .

References

Li, Ming; Vitányi, Paul (1997). An introduction to Kolmogorov complexity and its applications. New York: Springer-Verlag. ISBN 0387948686.